//
// Created by PC on 2017/12/20.
//

#ifndef VERTEXADJACENTITERATOR_DENSEGRAPH_H
#define VERTEXADJACENTITERATOR_DENSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
/*
 * 邻接矩阵，稠密图
 */
class DenseGraph{
private:
    int n,m;//节点数和边数
    bool directed;
    vector<vector<bool>> g;
public:
    DenseGraph(int n, bool directed) {
        assert(n>0);
        this->n=n;
        this->m=0;
        this->directed=directed;
        g=vector<vector<bool> > (n, vector<bool>(n, false));

    }
    ~DenseGraph(){}
    int V(){ return n; }
    int E(){ return m; }

    void addEdge(int v, int w) {
        assert(v>=0&&v<n);
        assert(w>=0&&w<n);
        //排除自环边
        //排除平行边
        if(v==w||g[v][w])
            return;
        g[v][w]=true;
        if(!directed)
            g[w][v]=true;
        m++;
    }
    class adjIterator{
    private:
        DenseGraph &G;
        int v;
        int index;
    public:
        adjIterator(int v,DenseGraph &graph):G(graph){
            assert(v>=0&&v<G.n);
            this->v=v;
            this->index=-1;
        }
        ~adjIterator(){}

        int begin(){
            index = -1;
            return next();
        }
        int next(){

            for (index += 1; index < G.V();index++) {
                if(G.g[v][index])
                    return index;
            }
                return -1;
        }

        bool end(){
            return index>=G.V();
        }
    };
};
#endif //VERTEXADJACENTITERATOR_DENSEGRAPH_H
